package array.leetcode.medium;

/**
 * @author bruin_du
 * @description 乘积小于 K 的子数组
 * @date 2022/8/3 16:30
 **/
public class OfferII009_NumSubarrayProductLessThanK {
    //这里还是用滑动窗口
    //值得注意的是这里不是求窗口的长度,而是求包含元素个数
    //很巧的是比如当前窗口内有 a,b,c 我们加入d，那么新增的个数是(d)(c,d)(b,c,d)(a,b,c,d)
    //可以发现这个组合个数和当前窗口大小是一样的
    //所以滑动窗口依旧适用
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0, product = 1,left = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            product *= nums[i];
            while (left <= i && product >= k) {
                product /= nums[left];
                left++;
            }
            res += i - left + 1;
        }
        return res;
    }
}
